Vĩnh Thạnh vốn là những làng của người dân tộc Bana. Khoảng đầu thế kỷ XVIII, người Kinh lên vùng đất này lập nghiệp dựng xóm ấp cho đến cuối năm 1945, những làng vùng này thuộc Tổng Vĩnh Thạnh của huyện Bình Khê (nay là huyện Tây Sơn) và Tổng Kim Sơn của huyện Hoài Ân.

Tháng 4 năm 1947, tỉnh Bình Định lập 4 huyện miền núi: Vân Canh, Vĩnh Thạnh, Kim Sơn và An Lão. Tên huyện Vĩnh Thạnh bắt đầu từ đó.

Khoảng cuối năm 1952, theo chủ trương của Khu 5, huyện Vĩnh Thạnh nhập vào tỉnh Gia-Kon đến tháng 7 năm 1954 lại trở về thuộc tỉnh Bình Định. Khi đó, huyện Vĩnh Thạnh gồm 50 làng thuộc 11 xã: Vĩnh An, Vĩnh Hòa, Vĩnh Hiệp, Vĩnh Hảo, Vĩnh Kim, Vĩnh Châu, Vĩnh Trường, Vĩnh Bình, Vĩnh Nghĩa, Vĩnh Hưng và Vĩnh Thuận.

Năm 1961, nhằm động viên nhân dân bước vào cuộc chiến đấu mới chống giặc Mỹ xâm lược và để giữ bí mật, lãnh đạo tỉnh đã lấy tên sông núi, tên người có công đặt tên cho xã (như núi Yang Điêng thay cho tên gọi xã Vĩnh Hiệp, suối LơPin là xã Vĩnh Trường, Bok Toih là xã Vĩnh Bình …) và các chữ cái kèm con số đặt tên cho một số làng từ đó mới có các tên mật danh: M6 (làng Lơ Ye), K11 (Kon Kriêng), N3 (Đe Klăng), O5 (Kon Trinh) …

Trong suốt cuộc kháng chiến chống Mỹ cứu nước (1954-1975) do đòi hỏi của các công tác chống địch và sản xuất, việc tách, nhập làng ở Vĩnh Thạnh luôn luôn xảy ra (cuối năm 1955 toàn huyện có 60 làng đến năm 1971 còn 40 làng đến năm 1974 là 45 làng).

Năm 1976, hai huyện Vĩnh Thạnh và Bình Khê hợp thành huyện Tây Sơn.

Năm 1982, lập lại huyện Vĩnh Thạnh gồm 6 xã trong đó có 5 xã miền núi (Vĩnh Sơn, Vĩnh Kim, Vĩnh Hảo, Vĩnh Hiệp, Vĩnh Hòa) và xã trung du Bình Quang.

Năm 1986, tỉnh điều chỉnh địa giới 3 xã Bình Quang, Vĩnh Hiệp, Vĩnh Hảo thành 4 xã: Vĩnh Hiệp, Vĩnh Hảo, Vĩnh Thịnh, Vĩnh Quang.

Ngày 7 tháng 11 năm 1986, Hội đồng Bộ trưởng ban hành quyết định 137-HĐBT[2]. Theo đó, chia ba xã Bình Quang, Vĩnh Hảo và Vĩnh Hiệp thành bốn xã lấy tên xã Vĩnh Hảo, xã Vĩnh Hiệp, xã Vĩnh Quang và xã Vĩnh Thịnh.

Ngày 14 tháng 12 năm 1991, Ban Tổ chức Chính phủ ban hành quyết định số 659-TCCP[3]. Theo đó:

• Tách 6.237 ha diện tích tự nhiên và 203 nhân khẩu của xã Vĩnh Kim; 4.194 ha diện tích tự nhiên và 496 nhân khẩu của xã Vĩnh Hảo và 1.015 ha diện tích tự nhiên của xã Vĩnh Hiệp để di chuyển dân cư xã Vĩnh Hòa về địa điểm mới, từ đó xã Vĩnh Hòa bị giải thể.
• Giao 5.337 ha diện tích tự nhiên vùng hồ thủy lợi Thuận Ninh (trước đây là địa điểm của xã Vĩnh Hòa) cho Ủy ban Nhân dân huyện Vĩnh Thạnh quản lý.

Ngày 15 tháng 11 năm 2005, Chính phủ ban hành Nghị định 143/2005/NĐ-CP[4]. Theo đó:

• Điều chỉnh 3.204,17 ha diện tích tự nhiên và 309 nhân khẩu của xã Vĩnh Sơn về xã Vĩnh Kim quản lý.
• Điều chỉnh 3.607,75 ha diện tích tự nhiên của xã Vĩnh Kim về xã Vĩnh Sơn quản lý.
• Điều chỉnh 3.690,94 ha diện tích tự nhiên của xã Vĩnh Kim về xã Vĩnh Hảo quản lý.
• Điều chỉnh 941 nhân khẩu của xã Vĩnh Kim về xã Vĩnh Quang.
• Điều chỉnh 6.072,2 ha diện tích tự nhiên của xã Vĩnh Hoà về xã Vĩnh Hảo quản lý.
• Điều chỉnh 1.828 ha diện tích tự nhiên của xã Vĩnh Hoà về xã Vĩnh Hiệp quản lý.
• Điều chỉnh 1.258 nhân khẩu của xã Vĩnh Hoà về xã Vĩnh Thịnh.
• Điều chỉnh 131,58 ha diện tích tự nhiên và 689 nhân khẩu của xã Vĩnh Hảo về xã Vĩnh Quang quản lý.
• Thành lập xã Vĩnh Thuận trên cơ sở điều chỉnh 3.534,53 ha diện tích tự nhiên và 1.341 nhân khẩu của xã Vĩnh Quang.
• Thành lập thị trấn Vĩnh Thạnh - thị trấn huyện lỵ của huyện Vĩnh Thạnh trên cơ sở điều chỉnh 936,49 ha diện tích tự nhiên và 5.874 nhân khẩu của xã Vĩnh Quang.
• Thành lập xã Vĩnh Hoà trên cơ sở điều chỉnh 929,12 ha diện tích tự nhiên và 1.335 nhân khẩu của xã Vĩnh Thịnh; 2.003,58 ha diện tích tự nhiên và 702 nhân khẩu thuộc xã Tây Thuận, huyện Tây Sơn.

Hiện nay, toàn huyện có 57 thôn, làng nằm trong 8 xã, 1 thị trấn: Vĩnh Sơn, Vĩnh Kim, Vĩnh Hảo, Vĩnh Hòa, Vĩnh Thuận, Vĩnh Hiệp, Vĩnh Quang, Vĩnh Thịnh và thị trấn Vĩnh Thạnh.